'''
单向循环链表
'''


class SingleNode(object):
    '''节点'''

    def __init__(self, item):
        self.item = item
        self.next = None


class SingleCycleLinkList(object):
    '''单向循环链表'''

    def __init__(self, obj=None):
        node = self.__get_node(obj)
        self.__head = node
        if node is not None:
            node.next = node

    def __get_node(self, obj):
        if obj is None:
            return None
        elif isinstance(obj, SingleNode):
            return obj
        else:
            return SingleNode(obj)

    def is_empty(self):
        return self.__head == None

    def length(self):
        if self.__head is None:
            return 0
        else:
            count = 1
            current = self.__head
            while current.next != self.__head:
                count += 1
                current = current.next
            return count

    def travel(self):
        '''遍历单向循环链表'''
        if self.is_empty():
            return
        current = self.__head
        print('start travel')
        while current.next != self.__head:
            print(current.item)
            current = current.next
        print(current.item, '\nend')

    def add(self, item):
        node = self.__get_node(item)
        if self.__head is None:
            self.__head = node
            node.next = node
        else:
            current = self.__head
            while current.next != self.__head:
                current = current.next
            current.next = node
            node.next = self.__head

    def append(self, item):
        node = self.__get_node(item)
        if self.is_empty():
            self.__head = node
            node.next = node
        else:
            current = self.__head
            while current.next != self.__head:
                current = current.next
            current.next = node
            node.next = self.__head

    def insert(self, pos, item):
        '''任意位置插入'''
        node = self.__get_node(item)
        if self.is_empty():
            self.__head = node
            node.next = node
        elif pos <= 0:
            '''头部插入'''
            if self.__head == self.__head.next:
                '''只有一个元素'''
                self.__head.next = node
                node.next = self.__head
                self.__head = node
            else:
                current = self.__head
                while current.next != self.__head:
                    current = current.next
                node.next = self.__head
                self.__head = node
                current.next = node
        else:
            count = 0
            current = self.__head
            while current.next != self.__head:
                count += 1
                if count == pos:
                    node.next = current.next
                    current.next = node
                    return
                else:
                    current = current.next
            if pos >= count:
                current.next = node
                node.next = self.__head

    def remove(self, item):
        '''删除指定元素'''
        if self.is_empty():
            return
        current = self.__head
        prev = None
        while current.next != self.__head:
            if current.item == item:  # 找到
                if self.__head == current:  # 头结点
                    # 找到尾节点
                    gear = self.__head
                    while gear.next != self.__head:
                        gear = gear.next
                    gear.next = current.next
                    self.__head = gear.next
                else:
                    prev.next = current.next
                return
            else:
                prev = current
                current = current.next

        if current.item == item:  # 尾节点是要删除的元素
            if prev is not None:
                prev.next = current.next
            else:  # 只有一个节点
                self.__head = None

    def search(self, item):
        '''查找'''
        if self.__head is None:
            return False
        current = self.__head
        while current.next != self.__head:
            if current.item == item:
                return True
            else:
                current = current.next
        if current.item == item:
            return True
        return False


if __name__ == '__main__':
    cll = SingleCycleLinkList()
    # cll.insert(10, 21)
    # cll.insert(0, 11)
    cll.insert(0, 2)
    cll.insert(1, 1)
    cll.travel()
    cll.remove(1)
    print('after:')
    cll.travel()
